
#ifndef PREFIX_TREE_HEADER
#define PREFIX_TREE_HEADER

#include "nedtrie.h"

#include <string.h> /* memset */
#include <unistd.h> /* close */

#ifdef __cplusplus
extern "C" {
#endif

typedef struct evnode_s evnode;
typedef struct tgssmc_s psa;

#include "dlinkedlist.h"
#include "path.h"

/* Define the list here                                                  */
/* Create the Double linked lists data structure to store one double     */
DLNODE(clock_n, double *);
DLLIST(clock_l, clock_n);

void clock_debug(clock_l *pl, clock_n *node);
/* --------------------------------------------------------------------- */

/* This block defines the NTRIE functions                                */
/* --------------------------------------------------------------------- */
typedef struct ntrieNode_s ntrieNode;
typedef struct ntrie_s ntrie;

struct ntrieNode_s {
  NEDTRIE_ENTRY(ntrieNode_s) link;
  size_t key;                      /* The event */
  evnode *node;                    /* Next node */
  double *clks;                    /* The clock sample of this event */
  unsigned int clks_size;
  unsigned int removed;
};

NEDTRIE_HEAD(ntrie_s, ntrieNode_s);

static size_t fookeyfunct(const struct ntrieNode_s *RESTRICT r)
{
  return r->key;
}

NEDTRIE_GENERATE(static, ntrie_s, ntrieNode_s, link, fookeyfunct, NEDTRIE_NOBBLEZEROS(ntrie_s));
/* --------------------------------------------------------------------- */

/* This block defines the inward set type and function                   */
/* --------------------------------------------------------------------- */
DLNODE(inward_n, ntrieNode *);
DLLIST(inward_l, inward_n);

GEN_DLINKEDLIST_FUNCTIONS_DECLARATION(dll_inward, inward_l, inward_n, ntrieNode *);
/* --------------------------------------------------------------------- */

/* This block defines the merge_heap functions                           */
/* --------------------------------------------------------------------- */
typedef struct heap_mg_el_s heap_mg_el;
typedef struct heap_mg_s heap_mg;

struct heap_mg_el_s {
  NEDTRIE_ENTRY(heap_mg_el_s) link;
  size_t key;
  evnode *x1;
  evnode *x2;
  ntrieNode *nt_x2;
  ntrie *t;
};

struct heap_mg_s {
  size_t count;
  struct heap_mg_el_s *triebins[NEDTRIE_INDEXBINS];
  int nobbledir;
  
  unsigned int id_heap;
};

static size_t merge_heap_key(const struct heap_mg_el_s *RESTRICT r) { return r->key; }
NEDTRIE_GENERATE(static, heap_mg_s, heap_mg_el_s, link, merge_heap_key, NEDTRIE_NOBBLEZEROS(heap_mg_s));
/* --------------------------------------------------------------------- */

struct evnode_s {
    unsigned int     nid;     /* Identification of node */
    unsigned int     ntimes;  /* Is the times number of event ocurrs in this evnode */
    unsigned int     deg;     /* Node degree */
    
    unsigned int     eid;     /* Identification of event; evnode represent an event */
    evnode           *parent;      /* Parent of this evnode */
    ntrieNode        *nt_node;     /* list node in the parent child node list */
    clock_l          *clk_samples; /* List allocating the clock samples; ntimes = size(G)*/
    
    ntrie            *child;       /* List of child nodes that this evnode has */
    inward_l         *inward;      /* List of input transitions excluding nt_node */
    
    unsigned int     removed;
    evnode           *remp;
};

struct distribution {
    unsigned int dist;
	double dist_parameters[3];
};

struct tgssmc_s {
    unsigned int     n;
    unsigned int     nodeArraySize;
    
    evnode           *root;   /* The root trie node */
    evnode           **nodeArray;
    
    heap_mg          *h_mg;
    
    struct distribution *parameters;
};


/* Public funtions */
psa *pt_create();

ntrie *pt_create_nt();
static ntrieNode *pt_create_ntrienode(evnode *node, unsigned int event);
ntrieNode *pt_create_node_nt2(unsigned int key);
ntrieNode *pt_change_node_nt(ntrieNode *node_nt, evnode *node);

heap_mg_el *create_heap_mg_el(heap_mg *heap, evnode *x1, evnode *x2);

void pt_insert(psa *trie, path_l *path);
void pt_sort(psa *trie);
int evnodecmp_c(evnode *n1, evnode *n2);
void normalize_inward(psa *trie);

void pt_debug_trieNodes(psa *trie);

/* Private funtions */
static evnode *pt_evnode(psa *trie, path_l *path, evnode *parent);
static void pt_search(psa *trie, path_l *path, unsigned int i, path_n *p, evnode *node, evnode *nodechild);
static int cmp_dln(const void *p1, const void *p2);
void pt_free_node(evnode *node);
void pt_free_prefix_tree(psa *trie);

void pt_debug(psa *trie);


/*static evnode *has_child(DoublyLinkedList *nodelist, unsigned int eid);*/
/*void tr_tofile(psa *trie, char *filename);
void tr_tofile2(FILE *dot, evnode *node, char *path);*/
/*void tr_debug(psa *trie);*/
/*void tr_debug2(DoublyLinkedList *nodelist, int i);*/

#ifdef __cplusplus
}
#endif

#endif
